package j2025.j05;

import java.util.*;

/**
 * @Author 猫大仙
 */
public class j0516 {
    int left,right,nn;
    List<String> ret;
    StringBuilder path;
    public List<String> generateParenthesis(int n) {
        left = 0;right = 0;
        nn = n;
        ret = new ArrayList<>();
        path = new StringBuilder();
        dfs();
        return ret;
    }
    public void dfs(){
        if(right==nn){
            ret.add(path.toString());
            return;
        }
        if(left<nn){
            path.append("(");
            left++;
            dfs();
            path.deleteCharAt(path.length()-1);
            left--;
        }
        if(right<left){
            path.append(")");
            right++;
            dfs();
            path.deleteCharAt(path.length()-1);
            right--;
        }
    }

    int[] dx = new int[]{0,0,-1,1};
    int[] dy = new int[]{1,-1,0,0};
    boolean[][] vis;
    int m,n;
    public boolean exist(char[][] board, String word) {
        m =board.length;n = board[0].length;
        vis = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(board[i][j] == word.charAt(0)){
                    vis[i][j] = true;
                    if(isOrNot(board,word,i,j,1)){
                        return true;
                    }
                    vis[i][j] = false;
                }
            }
        }
        return false;
    }
    public boolean isOrNot(char[][] board, String word,int i,int j,int index) {
        if(index == word.length()){
            return true;
        }
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if(x>=0 && x<m && y>=0 && y<n && !vis[x][y] && board[x][y]==word.charAt(index)){
                vis[x][y] = true;
                if(isOrNot(board,word,x,y,index+1)){
                    return true;
                }
                vis[x][y] = false;
            }
        }
        return false;
    }




    public List<List<String>> partition(String s) {
        int len = s.length();
        List<List<String>> ret = new ArrayList<>();
        if (len == 0) {
            return ret;
        }
        Deque<String> path = new ArrayDeque<>();
        char[] str = s.toCharArray();
        dfs(str, 0, len, path, ret);
        return ret;
    }
    public void dfs(char[] str, int index, int len, Deque<String> path, List<List<String>> ret) {
        if(index == len){
            ret.add(new ArrayList<>(path));
            return;
        }
        for (int i = index; i < len; i++) {
            if(!isPalindrome(str,index,i)){
                continue;
            }
            path.addLast(new String(str,index,i-index+1));
            dfs(str,i+1,len,path,ret);
            path.removeLast();
        }
    }
    public boolean isPalindrome(char[] s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }


    List<List<String>> ret;
    char[][] path;
    boolean[] col;
    boolean[] dig1;
    boolean[] dig2;
    int nmax = 0;
    public List<List<String>> solveNQueens(int n) {
        ret =  new ArrayList<>();
        path = new char[n][n];
        col = new boolean[n];
        dig1 = new boolean[2*n];
        dig2 = new boolean[2*n];
        nmax = n;
        for (int i = 0; i < n; i++) {
            Arrays.fill(path[i],'.');
        }
        dfs(0);
        return ret;
    }
    public void dfs(int pos){
        if(pos==nmax){
            List<String> tmp = new ArrayList<>();
            for (int i = 0; i < nmax; i++) {
                tmp.add(new String(path[i]));
            }
            ret.add(new ArrayList<>(tmp));
        }
        for (int i = 0; i < nmax; i++) {
            if(col[i]==false && dig1[pos-i+nmax]==false && dig2[pos+i]==false){
                path[pos][i] = 'Q';
                col[i] = true;
                dig1[pos-i+nmax]=true;
                dig2[pos+i]=true;
                dfs(pos+1);
                col[i] = false;
                dig1[pos-i+nmax]=false;
                dig2[pos+i]=false;
                path[pos][i] = '.';
            }
        }
    }
}
